class Solution(object):
    def __init__(self):
        self.sums = None
        self.lower = None
        self.upper = None

    def countRangeSum(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        if len(nums)==0: return 0
        self.sums = [0] * len(nums)
        self.sums[0] = nums[0]
        for i in range(1, len(nums)):
            self.sums[i] = nums[i]+self.sums[i-1]
        self.lower = lower
        self.upper = upper
        return self.mergeSort(0, len(nums))
        
    def mergeSort(self, low, high):
        # high included, low excluded
        if high-low==0: return 0
        if high-low==1:
            if self.lower<=self.sums[low]<=self.upper: return 1
            else: return 0
        mid = (high+low)//2
        count = self.mergeSort(low, mid) + self.mergeSort(mid, high)
        m = mid
        n = mid
        for i in range(low, mid):
            while m<high and self.sums[m]-self.sums[i]<self.lower: m+=1
            while n<high and self.sums[n]-self.sums[i]<=self.upper: n+=1
            count += (n-m)
        self.merge(low, mid, high)
        return count

    def merge(self, low, mid, high):
        # only one list
        if mid==low: return
        if high==mid: return
        i = low
        j = mid
        buf = [None] * (high-low)
        k = 0
        while i<mid and j<high:
            if self.sums[i]<self.sums[j]:
                buf[k]=self.sums[i]
                i+=1
            else:
                buf[k]=self.sums[j]
                j+=1
            k+=1
        while i<mid:
            buf[k]=self.sums[i]
            i+=1
            k+=1
        while j<high:
            buf[k]=self.sums[j]
            j+=1
            k+=1
        for k in range(len(buf)):
            self.sums[low+k] = buf[k]

print(Solution().countRangeSum([-2, 5, -1], -2, 2))